#include<stdio.h>
int s[4][4]={0};
int p[4][4]={0};
int a[4][4]={
  16,0,0,13,
  0,0,11,0,
  9,0,0,0,
  0,15,0,1,
};
int text(int n)
{
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(p[i][j]==n)
				return 0;
		}
	}
	return 1;
}
void dfs(int x,int y)
{
	if(x==4){
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				printf("%d ",p[i][j]);
			}
			printf("\n");
		}
		return ;
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			p[i][j]=a[i][j];
			for(int k=1;k<17;k++){
				if(text(k)&&!a[i][j]&&!s[i][j]){
					s[i][j]=1;
					p[i][j]=k;
					if(j+1>=4)
						dfs(i+1,0);
					else
						dfs(i,j+1);
					s[i][j]=0;
				}
			}
		}
	}
}
int main()
{
	dfs(0,0);
	return 0;
} 
